<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    1023. Time Based Key-Value Store
   </h1>
   <p>
    Create a timebased key-value store class&nbsp;
    <code>
     TimeMap
    </code>
    , that supports two operations.
   </p>
   <p>
    1.
    <code>
     set(string key, string value, int timestamp)
    </code>
   </p>
   <ul>
    <li>
     Stores the
     <code>
      key
     </code>
     and
     <code>
      value
     </code>
     , along with the given
     <code>
      timestamp
     </code>
     .
    </li>
   </ul>
   <p>
    2.
    <code>
     get(string key, int timestamp)
    </code>
   </p>
   <ul>
    <li>
     Returns a value such that
     <code>
      set(key, value, timestamp_prev)
     </code>
     was called previously, with
     <code>
      timestamp_prev &lt;= timestamp
     </code>
     .
    </li>
    <li>
     If there are multiple such values, it returns the one with the largest
     <code>
      timestamp_prev
     </code>
     .
    </li>
    <li>
     If there are no values, it returns the empty string (
     <code>
      ""
     </code>
     ).
    </li>
   </ul>
   <p>
    &nbsp;
   </p>
   <div>
    <p>
     <strong>
      Example 1:
     </strong>
    </p>
    <pre>
<strong>Input: </strong>inputs = <span id="example-input-1-1">["TimeMap","set","get","get","set","get","get"]</span>, inputs = <span id="example-input-1-2">[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]</span>
<strong>Output: </strong><span id="example-output-1">[null,null,"bar","bar",null,"bar2","bar2"]</span>
<strong>Explanation: </strong><span id="example-output-1">&nbsp; 
TimeMap kv; &nbsp; 
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1 &nbsp; 
kv.get("foo", 1);  // output "bar" &nbsp; 
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar" &nbsp; 
kv.set("foo", "bar2", 4); &nbsp; 
kv.get("foo", 4); // output "bar2" &nbsp; 
kv.get("foo", 5); //output "bar2" &nbsp; 
</span>
</pre>
    <div>
     <p>
      <strong>
       Example 2:
      </strong>
     </p>
     <pre>
<strong>Input: </strong>inputs = <span id="example-input-2-1">["TimeMap","set","set","get","get","get","get","get"]</span>, inputs = <span id="example-input-2-2">[[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]</span>
<strong>Output: </strong><span id="example-output-2">[null,null,null,"","high","high","low","low"]</span>
</pre>
    </div>
   </div>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     All key/value strings are lowercase.
    </li>
    <li>
     All key/value strings have&nbsp;length in the range&nbsp;
     <code>
      [1, 100]
     </code>
    </li>
    <li>
     The
     <code>
      timestamps
     </code>
     for all
     <code>
      TimeMap.set
     </code>
     operations are strictly increasing.
    </li>
    <li>
     <code>
      1 &lt;= timestamp &lt;= 10^7
     </code>
    </li>
    <li>
     <code>
      TimeMap.set
     </code>
     and
     <code>
      TimeMap.get
     </code>
     &nbsp;functions will be called a total of
     <code>
      120000
     </code>
     times (combined) per test case.
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    1023. 基于时间的键值存储
   </h1>
   <p>
    创建一个基于时间的键值存储类&nbsp;
    <code>
     TimeMap
    </code>
    ，它支持下面两个操作：
   </p>
   <p>
    1.
    <code>
     set(string key, string value, int timestamp)
    </code>
   </p>
   <ul>
    <li>
     存储键&nbsp;
     <code>
      key
     </code>
     、值&nbsp;
     <code>
      value
     </code>
     ，以及给定的时间戳&nbsp;
     <code>
      timestamp
     </code>
     。
    </li>
   </ul>
   <p>
    2.
    <code>
     get(string key, int timestamp)
    </code>
   </p>
   <ul>
    <li>
     返回先前调用&nbsp;
     <code>
      set(key, value, timestamp_prev)
     </code>
     &nbsp;所存储的值，其中&nbsp;
     <code>
      timestamp_prev &lt;= timestamp
     </code>
     。
    </li>
    <li>
     如果有多个这样的值，则返回对应最大的&nbsp;&nbsp;
     <code>
      timestamp_prev
     </code>
     &nbsp;的那个值。
    </li>
    <li>
     如果没有值，则返回空字符串（
     <code>
      ""
     </code>
     ）。
    </li>
   </ul>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入：</strong>inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
<strong>输出：</strong>[null,null,"bar","bar",null,"bar2","bar2"]
<strong>解释：</strong>&nbsp; 
TimeMap kv; &nbsp; 
kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1 &nbsp; 
kv.get("foo", 1);  // 输出 "bar" &nbsp; 
kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） &nbsp; 
kv.set("foo", "bar2", 4); &nbsp; 
kv.get("foo", 4); // 输出 "bar2" &nbsp; 
kv.get("foo", 5); // 输出 "bar2" &nbsp; 

</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <pre><strong>输入：</strong>inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
<strong>输出：</strong>[null,null,null,"","high","high","low","low"]
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     所有的键/值字符串都是小写的。
    </li>
    <li>
     所有的键/值字符串长度都在&nbsp;
     <code>
      [1, 100]
     </code>
     &nbsp;范围内。
    </li>
    <li>
     所有&nbsp;
     <code>
      TimeMap.set
     </code>
     &nbsp;操作中的时间戳&nbsp;
     <code>
      timestamps
     </code>
     都是严格递增的。
    </li>
    <li>
     <code>
      1 &lt;= timestamp &lt;= 10^7
     </code>
    </li>
    <li>
     <code>
      TimeMap.set
     </code>
     和&nbsp;
     <code>
      TimeMap.get
     </code>
     &nbsp;函数在每个测试用例中将（组合）调用总计&nbsp;
     <code>
      120000
     </code>
     次。
    </li>
   </ol>
  </div>
 </body>
</html>